package com.practice.suffixtree;

import java.util.HashMap;
import java.util.Set;

public class LongestRepeatedSubstring {
	public String find(String string) {
		char[] c = (string + "$").toCharArray();
		TrieNode root = new TrieNode();
		for (int i=c.length-1; i>=0; i--) {
			TrieNode parent = root;
			for (int j=0; j<c.length-i; j++) {
				parent = parent.addChild(c[i+j]);
			}
		}
		
		return findLongestSub(root);
	}
	
	private String findLongestSub(TrieNode node) {
		int maxLen = 0;
		String maxStr = null;
		for (char c : node.keys()) {
			TrieNode child = node.get(c);
			String sub = findLongestSub(child);
			if (sub == null) {
				if (!child.hasMultiBranches()) continue;
				sub = "" + c;
			}
			else {
				sub = c + sub;
			}
			
			if (sub.length() > maxLen) {
				maxLen = sub.length();
				maxStr = sub;
			}
		}
		return maxStr;
	}
	
	private class TrieNode {
		private HashMap<Character, TrieNode> map;
		
		public TrieNode() {
			map = new HashMap<Character, TrieNode>();
		}
		
		public TrieNode addChild(char c) {
			if (!map.containsKey(c)) {
				map.put(c, new TrieNode());
			}
			return map.get(c);
		}
		
		public boolean hasMultiBranches() {
			return map.size() > 1;
		}
		
		public Set<Character> keys() {
			return map.keySet();
		}
		
		public TrieNode get(char c) {
			return map.get(c);
		}
	}
}
